package class07;

import java.util.Stack;

/**
 * 非递归实现二叉树的先序,中序,后序遍历
 * 1.任何递归函数都可以改成非递归模式
 * 2.自己设计压栈来实现
 */
public class Code02_UnRecursiveTraversalBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	//前序: 中 右 左
	public static void pre(Node head) {
		//0.特殊处理:先把头节点压入
		//后续操作循环
		//1.栈弹出即打印
		//2.弹出的节点如有右孩子则先压右
		//3.弹出的节点如有左孩子,再压左
		//中 左 右
		System.out.print("pre-order: ");
		if (head != null) {
			//准备栈
			Stack<Node> stack = new Stack<Node>();
			//先把头加入
			stack.add(head);
			//循环
			while (!stack.isEmpty()) {
				head = stack.pop();
				System.out.print(head.value + " ");
				//右不为null,则先压入
				if (head.right != null) {
					stack.push(head.right);
				}
				if (head.left != null) {
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}

	//中序: 左 中 右
	public static void in(Node head) {
		System.out.print("in-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || head != null) {
				if (head != null) {
					//先压入左边界
					stack.push(head);
					head = head.left;
				} else {
					//弹出节点打印
					head = stack.pop();
					System.out.print(head.value + " ");
					//头调整为右(如右还有左边界会继续上个if分支)
					head = head.right;
				}
			}
		}
		System.out.println();
	}

	//后序: 左 右 中
	public static void pos1(Node head) {
		System.out.print("pos-order: ");
		if (head != null) {
			//利用两个栈进行后续打印
			//1.先序打印方式,先压左再压右
			//2.将数据存入一个栈中
			//3.然后打印出来(逆序)
			//中 右 左 -> 左 右 中 (逆序完成)
			Stack<Node> s1 = new Stack<Node>();
			Stack<Node> s2 = new Stack<Node>();
			s1.push(head);
			while (!s1.isEmpty()) {
				head = s1.pop();
				s2.push(head);
				if (head.left != null) {
					s1.push(head.left);
				}
				if (head.right != null) {
					s1.push(head.right);
				}
			}
			while (!s2.isEmpty()) {
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

	//后序, 节省一个栈空间版本
	//左 右 中
	//h跟踪上次打印(处理)的节点, c为记录可以回退到的上个节点(待处理节点)
	public static void pos2(Node h) {
		//h先默认指向头节点
		System.out.print("pos-order: ");
		if (h != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			Node c = null;
			while (!stack.isEmpty()) {
				//c指向栈的头部节点(上个待处理节点),并未弹出
				c = stack.peek();
				//左树未处理完成,压左
				if (c.left != null && h != c.left && h != c.right) {
					stack.push(c.left);
					//右树未处理完成,压右
				} else if (c.right != null && h != c.right) {
					stack.push(c.right);
					//(无左右孩子)处理并记录位置(已处理节点)
				} else {
					//弹出打印
					System.out.print(stack.pop().value + " ");
					//h来到c的位置
					h = c;
				}
			}
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos1(head);
		System.out.println("========");
		pos2(head);
		System.out.println("========");
	}

}
